package 中等;

/*
* 下一个排列
* 力扣地址：https://leetcode-cn.com/problems/next-permutation/
* 实现获取下一个排列的函数，算法需要将给定数字序列重新排列成字典序中下一个更大的排列。
* 如果不存在下一个更大的排列，则将数字重新排列成最小的排列（即升序排列）。
* 必须原地修改，只允许使用额外常数空间。
* 以下是一些例子，输入位于左侧列，其相应输出位于右侧列。
* 1,2,3 → 1,3,2
* 3,2,1 → 1,2,3
* 1,1,5 → 1,5,1
* 思路：
* 第一种情况
* 数组倒数第一个元素小于倒数第二个元素，直接交换两个元素的位置
* 第二种情况
* 从倒数第2个元素开始，寻找左边元素小于右边元素的 zd
*   第一种情况 如果没有找到，说明数组是按降序排列，直接按升序排列即可
*   第二种情况 如果找到了，在从倒数第一个元素和zd元素之间开始寻找大于 zd 中的最小的数
* 将zd到倒数第一个元素按升序进行排序，保证数列是最小的。
* */

import com.sun.org.apache.xerces.internal.dom.DeepNodeListImpl;

import java.util.Arrays;

public class demo31 {

    public static void main(String[] args) {

//        int[] a = {1,3,2,5,1,7,2,9};
//        int[] a = {1,5,8,4,7,6,5,3,1};
//        int[] a = {1,2,3};
//        int[] a = {2,3,1};
        int[] a = {3,2,1};

        nextPermutation(a);

    }

    public static void nextPermutation(int[] nums) {

        int t;
        //数组中只有一个元素
        if (nums.length < 2)
            return;
        //第一种情况 左边元素大于右边元素
        if (nums[nums.length-1] > nums[nums.length-2]){
            t = nums[nums.length-1];
            nums[nums.length-1] = nums[nums.length-2];
            nums[nums.length-2] = t;
            System.out.println(Arrays.toString(nums));
            return;
        }

        //第二种情况
        int zd = 0;
        //1.寻找左边较大的数
        for (zd =nums.length-2;zd>0;zd--){

            if (nums[zd] > nums[zd-1])
                break;
        }
        zd--;

        //zd 如果为-1则表示数组为降序 可直接到 3.
        if (zd != -1) {
            //2.寻找右边比zd大一点的数
            int yd = -1;

            for (int j = nums.length - 1; j > zd; j--) {

                if (yd == -1) {

                    if (nums[zd] < nums[j]) {
                        yd = j;
                    }
                } else {
                    if (nums[yd] < nums[j])
                        continue;
                    else
                        yd = j;
                }
            }

            //交换两个的值
            t = nums[yd];
            nums[yd] = nums[zd];
            nums[zd] = t;

            System.out.println(nums[yd]);
        }

        //3.将zd右边的值升序排序

        for(int i=zd+1;i<nums.length;i++){

            for (int j=i;j<nums.length;j++){

                if (nums[i] > nums[j])
                {
                    t = nums[i];
                    nums[i] = nums[j];
                    nums[j] = t;
                }

            }

        }


        System.out.println(Arrays.toString(nums));

    }


}
